package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)515. 在每个树行中找最大值
 * (done)623. 在二叉树中增加一行
 * (done)814. 二叉树剪枝
 * (done)513. 找树左下角的值
 * @author: jie.deng
 * @time: 2019年3月15日 下午3:43:27
 */
public class MySolution0316 {
	
	/**
	 * 515. 在每个树行中找最大值
	 * 
     * 您需要在二叉树的每一行中找到最大的值。
     * 
     * 示例：
     * 
     * 输入: 
     * 
     *           1
     *          / \
     *         3   2
     *        / \   \  
     *       5   3   9 
     * 
     * 输出: [1, 3, 9]
	 * @param root
	 * @return
	 */
    public List<Integer> largestValues(TreeNode root) {
		List<Integer> maxList = new ArrayList<Integer>();
		if (root == null) {
			return maxList;
		}
		Queue<BinaryNodeAndNum> queue = new LinkedList<BinaryNodeAndNum>();
		queue.offer(new BinaryNodeAndNum(root, 1)); // 根结点的level = 1
		while (!queue.isEmpty()) {
			BinaryNodeAndNum poll = queue.poll();
			int curLevel = poll.num;
			TreeNode cur = poll.node;
			if (maxList.size() >= curLevel) {
				Integer maxNum = maxList.get(curLevel - 1);
				maxList.set(curLevel - 1, Math.max(maxNum, cur.val));
			} else {
				maxList.add(cur.val);
			}
			if (cur.left != null) {
				queue.offer(new BinaryNodeAndNum(cur.left, curLevel + 1));
			}
			if (cur.right != null) {
				queue.offer(new BinaryNodeAndNum(cur.right, curLevel + 1));
			}
		}
		return maxList;
    }
    
    /**
     * 623. 在二叉树中增加一行
     * 
     * 给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。
     * 
     * 添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
     * 
     * 将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。
     * 
     * 如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
     * 
     * 示例 1:
     * 
     * 输入: 
     * 二叉树如下所示:
     *        4
     *      /   \
     *     2     6
     *    / \   / 
     *   3   1 5   
     * 
     * v = 1
     * 
     * d = 2
     * 
     * 输出: 
     *        4
     *       / \
     *      1   1
     *     /     \
     *    2       6
     *   / \     / 
     *  3   1   5   
     * 
     * 示例 2:
     * 
     * 输入: 
     * 二叉树如下所示:
     *       4
     *      /   
     *     2    
     *    / \   
     *   3   1    
     * 
     * v = 1
     * 
     * d = 3
     * 
     * 输出: 
     *       4
     *      /   
     *     2
     *    / \    
     *   1   1
     *  /     \  
     * 3       1
     * 注意:
     * 
     * 输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
     * 输入的二叉树至少有一个节点。
     * @param root
     * @param v
     * @param d
     * @return
     */
    public TreeNode addOneRow(TreeNode root, int v, int d) {
		if (d == 1) {
			TreeNode treeNode = new TreeNode(v);
			treeNode.left = root;
			return treeNode;
		}
		Queue<BinaryNodeAndNum> queue = new LinkedList<BinaryNodeAndNum>();
		queue.offer(new BinaryNodeAndNum(root, 1)); // 根结点的level = 1
		while (!queue.isEmpty()) {
			BinaryNodeAndNum poll = queue.poll();
			TreeNode cur = poll.node;
			int curLevel = poll.num;
			if (curLevel < d-1) {
				if (cur.left != null) {
					queue.offer(new BinaryNodeAndNum(cur.left, curLevel + 1));
				}
				if (cur.right != null) {
					queue.offer(new BinaryNodeAndNum(cur.right, curLevel + 1));
				}
			} else {
				if (curLevel == d - 1) {
					TreeNode treeNode = new TreeNode(v);
					treeNode.left = cur.left;
					cur.left = treeNode;

					treeNode = new TreeNode(v);
					treeNode.right = cur.right;
					cur.right = treeNode;
				}
			}
		}
		return root;
    }
    
    /**
     * 814. 二叉树剪枝
     * 
     * 给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
     * 
     * 返回移除了所有不包含 1 的子树的原二叉树。
     * 
     * ( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
     * 
     * 示例1:
     * 输入: [1,null,0,0,1]
     * 输出: [1,null,0,null,1]
     *  
     * 解释: 
     * 只有红色节点满足条件“所有不包含 1 的子树”。
     * 右图为返回的答案。
     * 
     * 示例2:
     * 输入: [1,0,1,0,0,0,1]
     * 输出: [1,null,1,null,1]
     * 
     * 示例3:
     * 输入: [1,1,0,1,1,0,1,0]
     * 输出: [1,1,0,1,1,null,1]
     * 
     * 说明:
     * 
     * 给定的二叉树最多有 100 个节点。
     * 每个节点的值只会为 0 或 1 。
     * @param root
     * @return
     */
	public TreeNode pruneTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		postOrderTraversal(root.left, root);
		postOrderTraversal(root.right, root);
		if (root.val == 0 && root.left == null && root.right == null) {
			root = null;
		}
		return root;
	}
    
	private void postOrderTraversal(TreeNode node, TreeNode parentNode) {
		if (node == null) {
			return;
		}
		postOrderTraversal(node.left, node);
		postOrderTraversal(node.right, node);
		if (node.val == 0 && node.left == null && node.right == null) {
			if (parentNode.left == node) {
				parentNode.left = null;
			} else {
				parentNode.right = null;
			}
		}
	}

	/**
     * 513. 找树左下角的值
     * 
     * 给定一个二叉树，在树的最后一行找到最左边的值。
     * 
     * 示例 1:
     * 
     * 输入:
     * 
     *     2
     *    / \
     *   1   3
     * 
     * 输出:
     * 1
     *  
     * 
     * 示例 2:
     * 
     * 输入:
     * 
     *         1
     *        / \
     *       2   3
     *      /   / \
     *     4   5   6
     *        /
     *       7
     * 
     * 输出:
     * 7
     *  
     * 
     * 注意: 您可以假设树（即给定的根节点）不为 NULL。
     * @param root
     * @return
     */
	public int findBottomLeftValue(TreeNode root) {
		List<Integer> levelList = new ArrayList<Integer>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();	// 广度优先搜索，使用队列实现，先进先出
		queue.offer(root);
		while (!queue.isEmpty()) {
			levelList.clear();
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				levelList.add(node.val); // 遍历当前结点
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		return levelList.get(0);
	}
    
    
	class BinaryNodeAndNum {
		public TreeNode node;
		public int num;

		public BinaryNodeAndNum(TreeNode node, int num) {
			super();
			this.node = node;
			this.num = num;
		}

	}
}
